翻訳と辞書 Words near each other ・ Price index ・ Price Induction ・ Price intelligence ・ Price Island ・ Price King ・ Price Lake (Whatcom County, Washington) ・ Price level ・ Price limit ・ Price look-up code ・ Price markdown ・ Price mechanism ・ Price Medal ・ Price Memorial Hall ・ Price Mill, Virginia ・ Price Nunatak ・ Price of anarchy ・ Price of fairness ・ Price of Fame ・ Price of Glory ・ Price of gold ・ Price of Life ・ Price of Love ・ Price of Love (Bad English song) ・ Price of Love (film) ・ Price of oil ・ Price of Peace Catholic School ・ Price of stability ・ Price of Weed ・ Price on application ・ Price optimization Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Price of anarchy ： ウィキペディア英語版 Price of anarchy The Price of Anarchy (PoA) 〔E. Koutsoupias, C. H. Papadimitriou (''Worst-case equilibria'' ), STACS 99〕 is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination. Let efficiency in this case mean the average time for an agent to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases. Usually the system is modeled as a game and the efficiency is some function of the outcomes (e.g. maximum delay in a network, congestion in a transportation system, social welfare in an auction, ...). Different concepts of equilibrium can be used to model the selfish behavior of the agents, among which the most common is the Nash equilibrium. Different flavors of Nash equilibrium lead to variations of the notion of Price of Anarchy as Pure Price of Anarchy (for deterministic equilibria), Mixed Price of Anarchy (for randomized equilibria), and Bayes-Nash Price of Anarchy (for games with incomplete information). Solution concepts other than Nash equilibrium lead to variations such as the Price of Sinking.〔M. Goemans, V. Mirrokni, A. Vetta, ''(Sink equilibria and convergence )'', FOCS 05〕 The term Price of Anarchy was first used by Koutsoupias and Papadimitriou,〔 but the idea of measuring inefficiency of equilibrium is older.〔P. Dubey. Inefficiency of Nash equilibria. Math. Operat. Res., 11(1):1–8, 1986〕 The concept in its current form was designed to be the analogue of the 'approximation ratio' in an approximation algorithm or the 'competitive ratio' in an online algorithm. This is in the context of the current trend of analyzing games using algorithmic lenses (algorithmic game theory). ==Mathematical definition== Consider a game $G=(N,S,u)$, defined by a set of players $N$, strategy sets $S\_i$ for each player and utilities $u\_i:\; S\; \backslash rightarrow\; \backslash mathbb$ (where $S\; =\; S\_1\; \backslash times\; ...\; \backslash times\; S\_n$ also called set of outcomes). We can define a measure of efficiency of each outcome which we call welfare function $W:\; S\; \backslash rightarrow\; \backslash mathbb$. Natural candidates include the sum of players utilities (utilitarian objective) $W(s)\; =\; \backslash sum\_\; u\_i(s),$ minimum utility (fairness or egalitarian objective) $W(s)\; =\; \backslash min\_\; u\_i(s),$ ..., or any function that is meaningful for the particular game being analyzed and is desirable to be maximized. We can define a subset $E\; \backslash subseteq\; S$ to be the set of strategies in equilibrium (for example, the set of Nash equilibria). The Price of Anarchy is then defined as the ratio between the 'worst equilibrium' and the optimal 'centralized' solution: $PoA\; =\; \backslash frac$ Following the convention in approximation algorithms, if the function measure efficiency is, instead of a 'welfare' we want to 'maximize', a 'cost function' $C\; :\; S\; \backslash rightarrow\; \backslash mathbb$ we want to 'minimize' (delay in a network, for example) we use: $PoA\; =\; \backslash frac$ A related notion is that of the Price of Stability (PoS) which measures the ratio between the 'best equilibrium' and the optimal 'centralized' solution: $PoS\; =\; \backslash frac$ or in the case of cost functions: $PoS\; =\; \backslash frac$ We know that $1\; \backslash leq\; PoS\; \backslash leq\; PoA$ by the definition. It is expected that the loss in efficiency due to game-theoretical constraints is somewhere between 'PoS' and 'PoA'. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Price of anarchy」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.